// 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，
// 判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词

function wordBreak(s: string, wordDict: string[]): boolean {
    const wordSet = new Set<string>(wordDict);// 将单词表转换为哈希集合
    // dp数组：表示第n位是否可以被拆成单词表中单词组合
    const dp: boolean[] = new Array(s.length + 1).fill(false);
    dp[0] = true;// 初始化边界
    // 条件转移方程
    for (let i = 1; i <= s.length; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (dp[i] === true) break;// 防止重复计算
            let currStr: string = s.substring(j, i);// 截取子串
            // 当单词表中存在子串且子串的前j位对应dp数组为真
            if (wordSet.has(currStr) && dp[j] === true) {
                // 说明第n位的字符串可以被拆成单个单词和单词组合拼接的形式
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length];// 返回第n位的dp数组，因为字符串总共有n位
}

// 这道题正确解法是动态规划算法
// 个人认为直觉上不是很容易想到
// 我们假设要判断一个任意长的单词是否是单词组合
// 其实就是看这个单词是否能被拆成一个单词表单词和一个单词表子组合
// 而单词表子组合必然也满足可以拆成一个单词表单词和一个单词表子子组合
// 这就形成了一个套娃...重复的子问题我们就可以利用动态规划解法
// 首先我们用双指针来划分单词表单词和单词表子组合
// 用一个dp数组来存储记忆这个单词的对应位置能否成为单词拆分组合
// 若当前位数已经可以成为单词拆分组合就直接break，没必要继续扫描
// 最后返回第n位的dp数组，因为字符串总共有n位
